//1.暴力

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n=gas.size();
        for(int i=0;i<n;i++)
        {
            int tem=0;
            for(int step=0;step<=n;step++)
            {
                int index=(i+step)%n;
                tem=tem+gas[index]-cost[index];
                if(tem<0)
                {
                    //无法走
                    break;
                }
            }
            if(tem>=0)
            {
                return i;
            }
        }
        return -1;
    }
};

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n=gas.size();
        for(int i=0;i<n;i++)
        {
            //第一次要吗找到 要么找不到 找不到就更新i最多o(n)的事件复杂度
            int tem=0;
            for(int step=0;step<=n;step++)
            {
                int index=(i+step)%n;
                tem=tem+gas[index]-cost[index];
                if(tem<0)
                {
                    //优化 当走step发现到不了的时候
                    //此时的i+step就是最大走到的位置
                    //此时i+1最大也就走到i+step了
                    //因此我们直接下次直接从i+step+1开始就好了
                    //无法走
                    //跟新起点 注意这里不用考虑溢出 因为跟新起点后接着加step步哪里会进行对长度的检查
                    i=i+step;
                    break;
                }
            }
            if(tem>=0)
            {
                return i;
            }
        }
        return -1;
    }
};